/**
 * Created with IntelliJ IDEA.
 * Description :
 * User: $ {USER}
 * Date: $ {YEAR}-$ {MONTH}一$ { DAY}
 * Time: ${ TIME}
 */

/**
 * 题目：两两交换链表中的节点
 * 思路：遍历原链表，创建新节点、新链表来实现两两交换链表中的节点
 *     注意：不能用原链表来尾插，因为这样会改变原链表的节点顺序，以致失败。
 */
public class Test {

    public ListNode swapPairs(ListNode head) {
        // 创建一个新的链表，将交换后的节点尾插到新链表中
        ListNode newHead = new ListNode(-1);
        ListNode cur = newHead;
        ListNode cur1 = head;
        while (cur1 != null) {
            ListNode cur2 = cur1.next;
            if (cur2 != null) {
                cur.next = new ListNode(cur2.val);
                cur = cur.next;
                cur.next = new ListNode(cur1.val);
            } else {
                cur.next = new ListNode(cur1.val);
            }
            cur = cur.next;
            if (cur1 != null && cur1.next != null) {
                cur1 = cur1.next.next;
            } else {
                cur1 = null;
            }
        }
        return newHead.next;
    }

    public static void main(String[] args) {
        ListNode head4 = new ListNode(4);
        ListNode head3 = new ListNode(3, head4);
        ListNode head2 = new ListNode(2, head3);
        ListNode head1 = new ListNode(1, head2);
        //swapPairs(head1);
    }
    public static ListNode swapPairs1(ListNode head) {
        // 创建一个新的链表，将交换后的节点尾插到新链表中
        ListNode newHead = new ListNode(-1);
        ListNode cur = newHead;
        ListNode cur1 = head;
        int len = 0;
        while (cur1 != null) {
            len++;
            cur1 = cur1.next;
        }
        cur1 = head;
        while (cur1 != null) {
            ListNode cur2 = cur1.next;
            if (cur2 != null) {
                cur.next = cur2;
                cur = cur.next;
                cur.next = cur1;
                len -= 2;
            } else {
                cur.next = cur1;
                len--;
            }
            cur = cur.next;
            if (len == 0) {
                break;
            }
            if (cur1 != null && cur1.next != null) {
                cur1 = cur1.next.next;
            } else {
                cur1 = null;
            }
        }
        cur.next = null;
        return newHead.next;
    }
}



class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
